import java.time.Period;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2023-04-07
 * Time: 1:38
 */
public class Solution3 {
    public ListNode sortInList (ListNode head) {
        //借助优先级队列的特性，队列存储节点，然后按照顺序依次弹出顶点，就是一个排好序的链表
        PriorityQueue<ListNode > priorityQueue=new PriorityQueue<>((o1, o2) -> o1.val- o2.val);
        ListNode cur=head;
        while (cur!=null){
            priorityQueue.add(cur);
            cur=cur.next;
        }
        ListNode newH=new ListNode(-1);
        cur=newH;
        while (!priorityQueue.isEmpty()){
            cur.next=priorityQueue.poll();
            cur=cur.next;
        }
        //断掉原来的指向，因为cur走到最后了
        cur.next=null;
        return newH.next;
    }

}
